package io.zhengsh.vvip.leetcode.dfs;

public class Q213_house_robber_ii {

    class Solution {
        public int rob(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            if (nums.length == 1) {
                return nums[0];
            }
            if (nums.length == 2) {
                return Math.max(nums[0], nums[1]);
            }
            return Math.max(robRange(nums, 0, nums.length - 2), robRange(nums, 1, nums.length - 1));
        }

        private int robRange(int[] nums, int i, int m) {
            int first = nums[i], second = Math.max(nums[i], nums[i + 1]);
            for (int j = i + 2; j <= m; j++) {
                int temp = second;
                second = Math.max(first + nums[j], second);
                first = temp;
            }
            return second;
        }
    }
}
